
// https://leetcode.cn/problems/combinations/description/

class Solution
{
    vector<vector<int>> res;
    vector<int> path;
    int _n, _k;

public:
    vector<vector<int>> combine(int n, int k)
    {
        _n = n; _k = k;
        dfs(0, 1);
        return res;
    }

    void dfs(int depth, int idx)
    {
        if (depth == _k)
        {
            res.push_back(path);
            return;
        }

        for (int i = idx; i <= _n; ++i)
        {
            path.push_back(i);
            dfs(depth + 1, i + 1);
            path.pop_back();
        }
    }
};